Fast Fourier Transform

A Fast Fourier Transform (FFT) is, as the name suggests, a fast way to perform a Fourier transform of time-series or other sequential data. It exploits symmetries in the calculation of the Fourier transform in order to reuse intermediate results. Whereas a brute force version of Fourier transform is quandratic in the size of the input (N²), the FFT is log-linear (N log₂N). For example, for N=1024, FFT is around 100 times faster (1024/log₂(1024)).